//Cracking the coding interview (5th), 2_4
//Write code to partition a linked list around a value x, such that all nodes less than x com before all nodes greater than or equal to x.
//8:31PM

#include <iostream>
#include <list>
using namespace std;

int class_list(list<int> &ls, int x, list<int> &tls)
{
  int val;
  while(!ls.empty()) {
    val = ls.front();
    ls.pop_front();
    if (val < x)
      tls.push_front(val);
    else
      tls.push_back(val);
  }
  return 0;
}

int main(int argc, char *argv[])
{
  list<int> ls, tls;
  ls.push_back(1);
  ls.push_back(3);
  ls.push_back(5);
  ls.push_back(7);
  ls.push_back(2);
  ls.push_back(4);
  ls.push_back(6);
  ls.push_back(8);
  class_list(ls, 3, tls);

  list<int>::iterator iter;
  for (iter = tls.begin(); iter != tls.end(); iter++)
    cout << *iter << endl;

  tls.clear();
  return 0;
}
